package com.yangzhe.algorithm.c030;

// 数组中有2种数出现了奇数次，其他的数都出现了偶数次
// 返回这2种出现了奇数次的数
// 测试链接 : https://leetcode.cn/problems/single-number-iii/
public class Code05_DoubleNumber1_LeetCode {
	/**
	 * 设两个数分别为 a b
	 * 1. 先异或所有数字 得到 a 异或 b
	 * 2. 因为a != b，则a或者b右侧一定有一个是1另外一个是0。取 a ^ b 最右侧的 1，这里假设a 最右侧是 1
	 * 3. 如果 a最右侧的1 & num = 0，则代表这个数字可能是b，
	 * 4. 把可能是b的所有数异或，其他数字是偶数个，b是奇数个，则得到b
	 * 5. a ^ b的结果再异或 b，则得到a
	 */
	public static int[] singleNumber(int[] nums) {
		// 1. 得到 a ^ b
		int axorb = 0;
		for (int i = 0; i < nums.length; i++) {
			axorb ^= nums[i];
		}

		// 2. 获取最右侧的1, 这里假设a最右侧是1，b最右侧是0
		// Brian Kernighan算法
		int rightOne = axorb & (-axorb);
		// 3. 得到b
		int b = 0;
		for (int i = 0; i < nums.length; i++) {
			// 为零则可能是b
			if ((nums[i] & rightOne) == 0) {
				b ^= nums[i];
			}
		}

		return new int[] {b, b ^ axorb};
	}

}
